938. Range Sum of BST

給定一個二叉搜索樹（BST）的根節點 root，以及兩個整數 low 和 high，請你計算樹中值位於區間 [low, high] 之間的所有節點的值的總和。

解題步驟

1. 使用 DFS（深度優先搜索）進行樹的遍歷。
2. 根據當前節點的值，決定是否繼續遍歷左子樹或右子樹。
3. 當遇到空節點時結束遞歸，返回 0。

def rangeSumBST(root: TreeNode, low: int, high: int) -> int:
    if not root:
        return 0
    if root.val < low:
        return rangeSumBST(root.right, low, high)  # 只遍歷右子樹
    elif root.val > high:
        return rangeSumBST(root.left, low, high)  # 只遍歷左子樹
    else:
        # 如果節點的值在範圍內，累加節點值並遍歷左右子樹
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

解題過程中的關鍵點

• 利用二叉搜索樹的特性進行剪枝
  • 如果當前節點的值小於 low，則不需遍歷左子樹。
  • 如果當前節點的值大於 high，則不需遍歷右子樹。
• 處理邊界情況
  • 當根節點為空時，應直接返回 0。
  • 需要確保範圍內的所有值都被計入。

複雜度分析

• 時間複雜度：O(N)，其中 N 是樹中節點的數量。最壞情況下，可能需要遍歷整棵樹，但剪枝會減少遍歷的節點數量。
• 空間複雜度
  • 遞歸方法的空間複雜度是 O(h)，其中 h 是樹的高度，對於平衡的樹來說是 O(log N)，但最壞情況下可能是 O(N)。
  • 迭代方法的空間複雜度也是 O(h)，由於使用了堆疊來保存待處理的節點。